package com.leetcode.search.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/27 20:15
 */
public class NQueens_51 {

    private char[][] board;
    private int n;
    private final List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        if (n == 0) return res;
        this.n = n;
        board = new char[n][n];
        // 棋盘初始化
        for (int i = 0; i < n; i++)
            Arrays.fill(board[i], '.');
        backtrack(0);
        return res;
    }

    private boolean backtrack(int row) {
        if (row == n) return true;
        for (int i = 0; i < n; i++) {
            // 如果非法则寻找下一个
            if (!isValid(row, i)) continue;
            board[row][i] = 'Q';
            // 如果得到正确结果，则将当前棋盘添加到结果
            if (backtrack(row + 1)) addBoard();
            board[row][i] = '.';
        }
        return false;
    }

    // 将当前棋盘添加到答案
    private void addBoard() {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new String(board[i]));
        }
        res.add(list);
    }

    public boolean isValid(int y, int x) {
        // 验证正上方
        for (int i = y - 1; i >= 0; i--) {
            if (board[i][x] == 'Q') return false;
        }
        // 验证右上方
        for (int i = y - 1, j = x + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        // 验证左上方
        for (int i = y - 1, j = x - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 都没问题返回true
        return true;
    }

}
